Pohlig and Hellman discussed the significance of this problem for cryptographic systems [3]. It was concluded by Pohlig and Hellman that, if p−1 has only small prime factors, x can be computed in a time of the order of log2 p. However, if p−1 has a large prime factor p′, the search for x requires a time of the order p′ ·log p and may be untraceable. As an illustration, Pohlig and Hellman presented two large primes of the form p=2·p′+1, where p′ is also prime and wherep′=213·5·7·11·13·17·19·23·29·31·37·41·43·47·530.59+1  (2)orp′=2121·52·72·112·13·17·19·23·29·31·37·41·43·47·53·59+1.  (3)
In general, let p=2·p′+1, where p′ is prime andp′−1=2ε0·q1ε1·q2ε2· . . . ·qiεi· . . . ·qhεh,  (4)where ε0≥1 and, for 1≤i≤h, q1 denotes an odd prime and εi>0. Also, for 1≤i<h, 2<qi<qi+1.NOTE 1: Pohlig and Hellman observed that q1≠3. In fact p=2·p′+1=2·(p′−1)+3. Since p is prime, it must be gcd (3, p′−1)=1.NOTE 2: Let X denote the set of elements of G which are relatively prime to p−1 and let A denote the set of primitive roots modulo p. Then |X|=|A|=φ(p−1), where φ(n) denotes the Euler totient function.NOTE 3: The elements of X form a commutative (abelian) group under the operation of multiplication modulo p−1. An integer m≥1 has a primitive root if and only if m=1, 2, 4, pd or 2·pd, where p is prime number and a is a positive integer [1, p. 211]. When X is cyclic, there exist integers p which are primitive roots of X modulo p−1. When primitive roots of X exist, let Y denote the set of elements of X which are primitive roots of X modulo p−1.NOTE 4: Section VIII below shows that, when p′−1 can be described as in (4), X is cyclic only if ε0<3